//按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。 
//
// n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。 
//
// 给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。 
//
// 
// 
// 每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。 
// 
// 
//
// 
//
// 示例 1： 
// 
// 
//输入：n = 4
//输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
//解释：如上图所示，4 皇后问题存在两个不同的解法。
// 
//
// 示例 2： 
//
// 
//输入：n = 1
//输出：[["Q"]]
// 
//
// 
//
// 提示： 
//
// 
// 1 <= n <= 9 
// 
//
// Related Topics 数组 回溯 👍 1822 👎 0


package leetcode.editor.cn;

// [51]N 皇后

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class NQueens_51 {
    public static void main(String[] args) {
        Solution solution = new NQueens_51().new Solution();
        System.out.println(solution.solveNQueens(4));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public List<List<String>> solveNQueens(int n) {
            if (n < 1) {
                return new ArrayList<>();
            }
            ArrayList<List<String>> ans = new ArrayList<>();
            process(0, new int[n], n, ans);
            return ans;
        }

        private void process(int i, int[] record, int n, List<List<String>> ans) {
            if (i == n) {
                ans.add(getAnsString(record));
                return;
            }
            for (int j = 0; j < n; j++) {
                if (isValid(record, i, j)) {
                    record[i] = j;
                    process(i + 1, record, n, ans);
                    //这里不需要回溯是因为，每次判断只考虑前面已经摆好的，后面的位置不管是什么忽略不计，不影响结果
                    //从前向后判断
//                    record[i] = 0;
                }
            }
        }

        private List<String> getAnsString(int[] record) {
            ArrayList<String> list = new ArrayList<>();
            for (int j : record) {
                char[] chars = new char[record.length];
                Arrays.fill(chars, '.');
                chars[j] = 'Q';
                list.add(new String(chars));
            }
            return list;
        }

        private boolean isValid(int[] record, int i, int j) {
            for (int k = 0; k < i; k++) {
                if (j == record[k] || Math.abs(k - i) == Math.abs(record[k] - j)) {
                    return false;
                }
            }
            return true;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}